package com.chapter4.graph.undirect;

import java.util.Stack;

/** 
 * @ClassName: DepthFirstSearch
 * @Description: DFS深度优先搜索 
 * 
 * 应用：可达路径
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-25 上午4:20:14 
 *  
 */
public class DepthFirstSearch {

	//保存所有节点是否被访问的数组--true已访问，false未访问
	private boolean[] marked;
	
	//将之前经过的路径节点存储到数组。edge[m]=v表示从上一次访问路径是从v->m
	private int[] edgeTo;
	
	//初始路径
	private final int s;
	
	public DepthFirstSearch(Graph g,int s) {
		this.s=s;
		marked=new boolean[g.V()];
		edgeTo=new int[g.V()];
		dfs(g, s);
	}

	/**
	 * 
	* @Title: dfs 
	* @Description: 在图g中，从v节点开始搜索路径 
	* @param @param g
	* @param @param v    设定文件 
	* @return void    返回类型 
	* @throws
	 */
	private void dfs(Graph g,int v){
		//将目前到达的节点设置为已经访问过
		marked[v]=true;
		//遍历所有相连节点
		for(int w:g.adj(v)){
			//如果没有访问过，才能进行访问
			if(!marked[w]){
				//铺设一条从v->w的访问路径
				edgeTo[w]=v;
				//递归访问指定节点
				dfs(g, w);
			}
		}
	}
	
	/**
	 * 
	* @Title: hasPathTo 
	* @Description: s->v之间是否有路径连通
	* @param @param v
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	/**
	 * 
	* @Title: pathTo 
	* @Description: 获取从s->v的路径 
	* @param @param v
	* @param @return    设定文件 
	* @return Iterable<Integer>    返回类型 
	* @throws
	 */
	public Iterable<Integer> pathTo(int v){
		if(!hasPathTo(v)){
			System.out.println("从初始点到达"+v+"节点之间没有访问路径");
			return null;
		}
		//倒序从v开始获取到s的返回路径，并将倒序获取的途径节点放置到Stack里面，使得客户在迭代路径的时候能够拿到一个正序s->v的路径(根据Stack的先进后出的原则)
		Stack<Integer> path=new Stack<Integer>();
		for(int i=v;i!=s;i=edgeTo[i]){
			path.push(i);
		}
		//最后别忘了将起始节点添加到Stack的头部
		path.push(s);
		return path;
	}
	
	
	public void printEdgeArray(){
		for(int i=0;i<edgeTo.length;i++){
			System.out.println(i+"<-"+edgeTo[i]);
		}
	}
}
